package th.retrofit.lib;

import java.util.ArrayList;

/**
 * https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
 * 给定一棵树的前序遍历 preorder 与中序遍历  inorder。请构造二叉树并返回其根节点
 */
public class Solution105 {

    int iIndex = 0;
    int pIndex = 0;

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder == null || preorder.length == 0) return null;
        return buildTree1(preorder, inorder, Integer.MAX_VALUE);
    }

    public TreeNode buildTree1(int[] preorder, int[] inorder, int val) {
        if (pIndex >= preorder.length || iIndex >= preorder.length) return null;
        if (pIndex > 0 && inorder[iIndex] == val) {
            iIndex += 1;
            return null;
        }
        int curVal = preorder[pIndex++];
        TreeNode cur = new TreeNode(curVal);
        cur.left = buildTree1(preorder, inorder, curVal);
        cur.right = buildTree1(preorder, inorder, val);
        return cur;
    }

    public static void main(String[] args) {
        int[] preOrder = new int[]{3,9,5,1,2};
        int[] inOrder = new int[]{9,1,5,2,3};
        TreeNode node = new Solution105().buildTree(preOrder, inOrder);
        System.out.println(node);
    }

}
